class Go:
    def __init__(self):
        self.size = (19, 19)
        self.board = [[0] * self.size[1] for i in range(self.size[0])]
        self.pj = []  # 可能打劫的位置

    def step(self, t, s):
        x = s[0]
        y = s[1]

        if not self.is_legal_1(s):
            return False

        if s in self.pj:
            # 不能下在可能打劫的地方
            return False

        # 不能不入气，除非能够提子
        # 试下
        self.board[x][y] = t
        block = self.cal_block(s)
        breath = self.cal_breath(block)

        # 看是否能够提子
        can_drop = False
        can_clear = True
        ts = [(s[0], s[1] - 1), (s[0], s[1] + 1), (s[0] - 1, s[1]), (s[0] + 1, s[1])]  # 左右上下
        for t1 in ts:
            if self.is_legal_2(t1) and self.board[t1[0]][t1[1]] == -t:
                block1 = self.cal_block(t1)
                breath1 = self.cal_breath(block1)
                if breath1 == 0:
                    # 提子
                    self.drop_chess(block1)
                    if len(block1) == 1:
                        self.pj.append(block1[0])
                        can_clear = False
                    can_drop = True
        if breath == 0 and (not can_drop):
            # 不能提子，恢复原状
            self.board[x][y] = 0
            return False
        if can_clear: self.clear_pj()
        return True

    def is_legal_1(self, t):
        # 不能落在有子或棋盘之外
        x = t[0]
        y = t[1]
        if x >= self.size[0] or y >= self.size[1] or self.board[x][y] != 0:
            return False
        return True

    def is_legal_2(self, t):
        # 不能落在棋盘之外
        x = t[0]
        y = t[1]
        if x >= self.size[0] or y >= self.size[1]:
            return False
        return True

    def cal_block(self, m):
        # 搜索
        x = m[0]
        y = m[1]
        assert x < self.size[0] and y < self.size[1]
        assert self.board[x][y] != 0
        v = self.board[x][y]  # 代表子的颜色
        s = [(x, y)]
        search = [(x, y)]
        while True:
            new_search = []
            for t in search:
                ps = [(t[0], t[1] - 1), (t[0], t[1] + 1), (t[0] - 1, t[1]), (t[0] + 1, t[1])]  # 左右上下
                for p in ps:
                    if self.is_legal_2(p) and self.board[p[0]][p[1]] == v:
                        if p not in s:
                            if p not in new_search:
                                new_search.append(p)
                            s.append(p)
            if len(new_search) == 0: break
            search = new_search
        return s

    def cal_breath(self, s):
        all_breath = []
        for t in s:
            ps = [(t[0], t[1] - 1), (t[0], t[1] + 1), (t[0] - 1, t[1]), (t[0] + 1, t[1])]  # 左右上下
            for p in ps:
                if self.is_legal_2(p) and self.board[p[0]][p[1]] == 0 and p not in all_breath:
                    all_breath.append(p)
        return len(all_breath)

    def drop_chess(self, block):
        for t in block:
            self.board[t[0]][t[1]] = 0

    def print_board(self):
        for line in self.board:
            for e in line:
                if e == 0: print("-", end='')
                if e == 1: print("X", end='')
                if e == -1: print("O", end='')
            print()

    def __str__(self):
        s = ""
        for line in self.board:
            for e in line:
                if e == 0: s += "-"
                if e == 1: s += "X"
                if e == -1: s += "O"
            s += "\n"
        return s

    def clear_pj(self):
        self.pj.clear()

